package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/construct-string-from-binary-tree">根据二叉树创建字符串(Construct String from Binary Tree)</a>
 * <p>给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。</p>
 * <p>空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。</p>
 * </p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4]
 *                  1
 *                 / \
 *                2   3
 *               /
 *              4
 *      输出："1(2(4))(3)"
 *      解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
 *
 * 示例 2：
 *      输入：root = [1,2,3,null,4]
 *                  1
 *                 / \
 *                2   3
 *                 \
 *                  4
 *      输出："1(2()(4))(3)"
 *      解释：和第一个示例类似，但是无法省略第一个空括号对，否则会破坏输入与输出一一映射的关系。
 * </pre>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目范围是 [1, 10^4]</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/23 16:24
 */
public class LC0606ConstructStringFromBinaryTree_S {

    static class Solution {
        public String tree2str(TreeNode root) {
            if (root == null) {
                return "";
            }
            // 如果左子节点右子节点都为null，可以省略括号
            if ((root.left == null && root.right == null)) {
                return Integer.toString(root.val);
            }
            // 左括号一定存在。右括号不一定存在
            StringBuilder res = new StringBuilder().append(root.val);
            res.append("(").append(tree2str(root.left)).append(")");
            if (root.right != null) {
                res.append("(").append(tree2str(root.right)).append(")");
            }
            return res.toString();
        }

        public String tree2str2(TreeNode root) {
            StringBuilder builder = new StringBuilder();
            tree2str2(root, builder);
            return builder.toString();
        }

        public void tree2str2(TreeNode root, StringBuilder path) {
            if (root == null) {
                return;
            }
            // 叶子节点：左子节点右子节点都为null
            path.append(root.val);
            if ((root.left == null && root.right == null)) {
                return;
            }
            // 左子节点不管是否为null，都需要括号
            path.append("(");
            tree2str2(root.left, path);
            path.append(")");
            // 右子节点只需要在有值的时候才需要括号
            if (root.right != null) {
                path.append("(");
                tree2str2(root.right, path);
                path.append(")");
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.tree2str(Generator.buildTree(1, 2, 3, 4)));
        System.out.println(solution.tree2str(Generator.buildTree(1, 2, 3, null, 4)));
    }
}